Field of the Invention
The invention relates to a computer implemented method optimizing a loop in a computer program. The method enables optimizing compilers to efficiently implement a code improving transformation that removes load statements from certain loops. This method may be performed upon rank-n static single assignment ("SSA") intermediate languages.
Most computer programmers write computer programs in source code using high-level languages such as C, FORTRAN, or PASCAL. While programmers may easily understand such languages, modern computers are not able to directly read such languages. Thus, such computer programs must be translated into a language, known as machine language, that a computer can understand. One step in the translating process is performed by a compiler. A compiler is a computer program that translates a source code program into object code. Object code is a machine language description of a high-level computer program. Object code produced by straight forward compiling algorithms can often be made to execute faster. This improvement is called optimization. Compilers that apply code-improving transformations are called optimizing compilers.
Some conventional optimizing compilers translate high-level computer programs into an intermediate language known as a Static Single Assignment (SSA) representation. This SSA intermediate language is used as a basis to perform certain optimizations. After these optimizations are performed, these conventional compilers translate the SSA intermediate language into optimized object code.
A statement in a computer program is said to "define" a variable if it assigns, or may assign, a value to that variable. For example, the statement "x=y+z" is said to "define" x. A statement that defines a variable contains a "definition" of that variable. In this context, there are two types of variable definitions: unambiguous definitions and ambiguous definitions. Ambiguous definitions may also be called complex definitions.
When a definition always defines the same variable, the definition is said to be an "unambiguous definition" of that variable. For example, the statement, "x=y" always assigns the value of y to x. Such a statement always defines the variable x with the value of y. Thus, the statement "x=y" is an "unambiguous definition" of x. If all definitions of a variable in a particular segment of code are unambiguous definitions, then the variable is known as an unambiguous variable.
Some definitions do not always define the same variable. However, these definitions may possibly define different variables at different times in a computer program. Thus, they are called "ambiguous definitions." There are many types of ambiguous definitions and the principal common denominator among the many types is that they are not unambiguous definitions. One type of "ambiguous definition" occurs where a pointer refers to a variable. For example, the statement "*p=y" may be a definition of x since it is possible that the pointer p points to x. Thus, the above ambiguous definition may ambiguously define any variable x if it is possible that p points to x. In other words, *p may define one of several variables depending on the value of p. Another type of ambiguous definition is a call of a procedure with a variable passed by reference. When a variable is passed by reference, the address of the variable is passed to the procedure. Passing a variable by reference to a procedure allows the procedure to modify the variable. Alternatively, variables may be passed by value. When a variable is passed by value, only the value of the variable is passed to'the procedure. Passing a variable by value does not allow the procedure to modify the variable. Still another type of ambiguous definition is a procedure that may access a variable because that variable is within the scope of the procedure. Another type of ambiguous definition occurs when a variable is not within the scope of a procedure but the variable has been identified with another variable that is passed as a parameter or is within the scope of the procedure.
When a statement in a computer program references a variable, the statement is said to "use" the variable. For example, the statement "x=y+z" refers to and is said to "use" y and z. Similarly, y and z (but not x) are "used" in the statement "x[y]=z." A statement that uses a variable contains a "use" of that variable.
A definition of a variable "reaches" a use of that variable if that definition is the last ambiguous or definite definition of that variable prior to the use. Consider the following straight-line C pseudo code.
x=6 PA1 x=x+5 PA1 x=7 PA1 x=x+8 PA1 t.sub.1 =6 PA1 t.sub.2 =t.sub.1 +5 PA1 t.sub.3 =7 PA1 t.sub.4 =t.sub.3 +8 PA1 if (p) then PA1 else PA1 x=2+x PA1 if (p) then PA1 else PA1 t.sub.3 =.PHI.(t.sub.1, t.sub.2) PA1 t.sub.4 =2+t.sub.3 PA1 Loop { . . . PA1 t.sub.1 =x; PA1 Loop { . . . PA1 Loop { . . .
The definition in the first statement "x=6" reaches the use in the second statement "x=x+5." Similarly, the definition in the third statement "x=7" reaches the use in the fourth statement "x=x+8." Note that the definition in the first statement does not reach the use of the fourth statement because x is redefined in the second and third statements.
In the above example, the definitions of x in the second and third statements are said to "kill" the definition of x in the first statement in that they nullify the effects of the definition in the first statement. Only unambiguous definitions of a variable can kill other definitions of the variable. Thus, a use can be reached by both an unambiguous definition and a subsequent ambiguous definition of the same variable.
A computer programmer may address a variable by specifying the variable's location in memory. This location is known as the variable's absolute address. This method of addressing is known as direct addressing. Direct addressing commonly occurs when a variable is specified by its name. For example, in the statement "y=x," both y and x are directly addressed.
A computer programmer may also address a variable by specifying an address that refers to a different address, which may specify yet another address. This method of addressing is known as indirect addressing. Common examples of indirect addressing include pointers, arrays and combinations of pointers and arrays. Examples of indirect addressing include a[i], *p, *(p+4), **p, a[b[i]], and *(*p+4). When a variable is indirectly addressed, at least one indirect memory reference is employed to determine the absolute address of the variable.
A variable may be classified based upon the number of indirect memory references employed to determine the absolute address of the variable. For example, as discussed above, y and x may be directly addressed. Thus, there are zero indirect memory references employed to determine the absolute address of both y and x. These variables are known as rank-0 variables.
A variable that requires a single indirect memory reference is known as a rank-1 variable. Examples of rank-1 variables include single pointer references and single array references such as a[i], *p, and *(p+4). A variable that requires two indirect memory references is known as a rank-2 variable. Rank-2 variables include double pointer references and double array references and the combination of a single pointer reference and a single array reference. Examples of rank-2 variables include **p, a[b[i]], and *(*p+4). A rank-n variable employs n indirect memory references to determine the absolute address of the variable.
A definition that defines a rank-n variable is known as a rank-n definition. Similarly a use of a rank-n variable is known as a rank-n use. For example, the definition of the array element b[a[i]] is a rank-0 use of the variable i, a rank-1 use of the array element a[i], and a rank-2 definition of the array element b[a[i]].
Returning to the discussion of SSA intermediate languages, when a computer program is conventionally translated into a SSA intermediate language, each variable definition is given a unique name. Further, all the uses reached by that definition are also renamed to match the variable's new name. For example, consider the straight-line C pseudo code discussed above. When this C pseudo code is translated into a SSA intermediate language, the result would be the following:
The symbols t.sub.1 through t.sub.4 represent compiler temporaries or even more commonly as temps. Unlike most variables, temps have only a single definition. Because a temp has only a single definition, it may not be defined by an ambiguous definition. Thus, temps are unaliasable scalars. Because temps are unaliasable scalars, an expression using t.sub.1 has a different symbolic meaning from the symbolic meaning of an otherwise identical expression using i. Every use of i cannot be considered equal because i represents an aliasable variable. However, every use of t.sub.1 can be considered equal. While a compiler may not be able to determine the value contained in a temp, every use of that temp will return the same unknown value. Therefore, temps dramatically simplify certain compiler algorithms.
Unlike the above straight-line C pseudo code, programs typically also contain branch statements. A branch statement is a statement that selects one set of statements from a number of alternative sets of statements. For example, consider the following if-then-else statement:
{x=4} PA2 {x=6} PA2 {t.sub.1 =4} PA2 {t.sub.2 =6} PA2 y=x+a PA2 . . } PA2 y=t.sub.1 +a PA2 . . } PA2 *p=4 PA2 y=x+a PA2 . . }
The flow of control through this code segment during execution will branch depending on whether p is true or false and will unite again at the statement "x=2+x." The point where the flow of control branches is known as the "branch point" and the point where it unites is known as the "join point" or the "confluence point."
When this C pseudo code is translated into a SSA intermediate language, the result would be the following:
Depending on the value of p, either t.sub.1 will be defined as 4 or t.sub.2 will be defined as 6. In order to "join" these two definitions, a special definition called a phi-function is inserted at the "join point" where the branches join. Phi-functions are known by those skilled in the art.
The above phi-function contains two operands. An operand is a quantity that enters into (or results from) an operation. The operands indicate which definitions reach the join point. In this example, both t.sub.1 and t.sub.2 reach the join point. Thus, both t.sub.1 and t.sub.2 are operands to the phi-function that defines t.sub.3. As shown above, subsequent uses of x in the original program would use t.sub.3 in the corresponding SSA intermediate language.
One or more of the above-listed related application Ser. No. 08/831,074, filed on even date herewith, describe a method of creating a rank-n SSA intermediate language from a rank-(n-1) SSA intermediate language, where n is a positive integer. The method includes searching the rank-(n-1) SSA intermediate language for rank-1 definitions that reach at least one use and renaming the rank-1 definitions and the at least one use. By repetitively performing this method, increasingly more complex symbolic expressions may be incorporated into a SSA intermediate language. A rank-n SSA intermediate language provides a uniquely simple framework for performing many manipulations and optimizations such as those described in the U.S. patent applications incorporation by reference above.
A widely held belief is that a computer program spends ninety percent of its execution time in ten percent of the program. While the actual percentages may vary, it is often the case that a small fraction of a computer program accounts for most of the execution time. A computer program often spends a large percentage of its time executing loops. A loop is a sequence of statements that is to be executed iteratively. Some modem structured languages have looping control constructs such as "while," "repeat," "goto," and "for" statements. Thus, these loops may be easily determined from the syntax of the program.
A loop typically has one entry point and one exit point. However, it may have several entry points and several exit points. An entry point is a statement in a loop. The only way to reach a statement in a loop is to first execute an entry point. An exit point is also a statement in a loop. The only way to reach a statement outside the loop from inside the loop is to go through an exit point. An exit point is the last statement executed in a loop.
Variables in high-level languages are an abstraction of memory locations. One of the compiler's tasks when translating a high-level computer language program into object code is to assign these abstract variables into physical locations.
An optimizing compiler that utilizes a SSA intermediate language typically attempts to assign as many variables as possible to temps. Because temps may be placed in registers, numerous loads and stores to/from external memory may often be eliminated. However, not all variables may be assigned to temps. In some circumstances a variable may be assigned to a location within external memory. The method that a compiler utilizes to assign variables to registers and memory locations in part determines the execution time of a computer program.
One conventional method of assigning variables to registers is to assign as many variables to registers as possible and then assign any remaining variables to external memory. Another method of assigning variables is to assign registers to the variables that have the greatest utilization and then assign any remaining variables to external memory. As was discussed above, variables within loops are often the most utilized variables. Consider the following loop that contains only unambiguous definitions.
A conventional optimizing compiler that utilizes a SSA intermediate language may optimize the above loop as follows.
In this loop, t.sub.1 would optimally be assigned to a register. Thus, the definition of t.sub.1 would load the variable x from external memory into the register assigned to t.sub.1. Note that the load of x is now outside of the loop. This optimization minimizes the number of loads from external memory and reduces the execution time of the loop.
As shown above, it is often optimal to move load instructions outside of a loop. However, utilizing conventional methods, it is not always possible to move such instructions outside of a loop. Consider the following C pseudo code loop.
The ambiguous definition of *p may modify the value of x. Thus, the variable x must be reloaded in subsequent instructions such as the instruction that defines y. As a result, conventional SSA compilers cannot assign the variable x to a temp outside the loop as discussed above. The resulting loop is not optimal. Thus, a need exists for a method to optimize a loop that contains an ambiguous definition prior to a use of a variable.